#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <queue>
#include <stdio.h>
using namespace std;

#define K 3      // 关键字最高位
#define RADIX 10 // 基数

// 构造RADIX个队列
queue<int> Q[RADIX];

int
GetKey(int value, int k)
{
  int key = 0;
  while (k >= 0) {
    key = value % 10;
    value /= 10;
    k--;
  }
  return key;
}

void
Distribute(int a[], int left, int right, int k)
{
  for (int i = left; i < right; ++i) {
    int key = GetKey(a[i], k);
    Q[key].push(a[i]);
  }
}

void
Collect(int a[])
{
  int j = 0;
  for (int i = 0; i < RADIX; ++i) {
    while (!Q[i].empty()) {
      a[j++] = Q[i].front();
      Q[i].pop();
    }
  }
}

/**
 * 基数排序
 */
void
RadixSort(int a[], int left, int right) // [left,right)
{

  /**
   * 完成K次分发和回收即可完成排序
   */
  for (int i = 0; i < K; ++i) {
    Distribute(a, left, right, i);
    Collect(a);
  }
}

int
main()
{
  int arr[] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83 };
  int n = sizeof(arr) / sizeof(arr[0]);
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  /*
   * 基数排序
   **/
  RadixSort(arr, 0, n);

  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");

  return 0;
}